Vehicles operating in an autonomous mode (e.g., driverless) can relieve occupants, especially the driver, from some driving-related responsibilities. When operating in an autonomous mode, the vehicle can navigate to various locations using onboard sensors, allowing the vehicle to travel with minimal human interaction or in some cases without any passengers.
Vehicles can navigate using reference lines. A reference line is a path that autonomous driving vehicles should drive along when there are no surrounding obstacles. One or more obstacles on a roadway can each have a trajectory. For each obstacle, the ADV may determine a projection of the trajectory of the obstacle onto the reference line of the ADV to make driving decisions based upon the proximity of the obstacle to the ADV reference line at multiple points along the trajectory of the obstacle. The time cost of computing a projection from a point (x,y) on a trajectory of an obstacle to a point on the reference line of the ADV is on the order of O(n), where n is the number of points on the trajectory of the obstacle. A planning module of the ADV needs to project the trajectory of each obstacle onto the reference line of the ADV to ensure that the ADV maintains a safe driving distance from each obstacle on the roadway. Determining a projection of an obstacle, such as a car, onto the reference line of the ADV is computationally expensive and can limit how often the projection can be performed for each obstacle. The computational complexity is further compounded when there is a substantial number of obstacles, such as cars, pedestrians, and other obstacles, in the proximity of the ADV.